// https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/

// 算法思路总结：
// 1. 深度优先搜索计算根到叶子节点的数字之和
// 2. 从根节点开始，累加路径上的数字（sum = sum * 10 + val）
// 3. 到达叶子节点时将当前路径值加入结果
// 4. 递归遍历左右子树，传递当前路径值
// 5. 时间复杂度：O(n)，空间复杂度：O(h)（递归栈深度）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int ret = 0;
    int sumNumbers(TreeNode* root) 
    {
        ret = 0;
        dfs(root, 0);
        return ret;
    }

    void dfs(TreeNode* root, int sum)
    {

        sum = sum * 10 + root->val;

        if (root->left == nullptr && root->right == nullptr)
        {
            ret += sum;
            return ;
        }
        
        if (root->left) dfs(root->left, sum);
        if (root->right) dfs(root->right, sum);

        return ;
    }
};

int main()
{
    vector<string> tree1 = {"1", "2", "3"};
    vector<string> tree2 = {"4", "9", "0", "5", "1"};
    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << sol.sumNumbers(root1) << endl;
    cout << sol.sumNumbers(root2) << endl;

    return 0;
}